#include<iostream>
#include<vector>

using namespace std;

class Trie {
public:
    Trie() :_children(26), is_end(false)
    {
    }

    void insert(string word) {
        auto cur = this;
        for (auto it : word)
        {
            int t = it - 'a';
            if (cur->_children[t] == nullptr)
                cur->_children[t] = new Trie();
            cur = cur->_children[t];
        }
        cur->is_end = true;
    }

    bool search(string word) {
        auto node = getSearch(word);
        return node != nullptr && node->is_end;
    }

    bool startsWith(string prefix) {
        auto node = getSearch(prefix);
        return node != nullptr;
    }
private:
    vector<Trie*> _children;
    bool is_end;

    Trie* getSearch(string word)
    {
        auto cur = this;
        for (auto it : word)
        {
            auto t = it - 'a';
            if (cur->_children[t] == nullptr)
                return nullptr;
            cur = cur->_children[t];
        }
        return cur;
    }
};